class Solution {
public:
    vector<vector<int>> result;
    vector<int> sol;

    void dfs(vector<int>& candidates, int target, int cur) {
        if (target < 0 || cur >= candidates.size()) return;
        if (target == 0) {
            result.push_back(sol);
            return;
        }

        dfs(candidates, target, cur + 1);

        sol.push_back(candidates[cur]);
        dfs(candidates, target - candidates[cur], cur);
        sol.pop_back();
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return result;
    }
};
